package class09;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *
 * 输入: 正数数组costs,正数数组profits,正数K,正数M
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * K表示你只能串行的最多做K个项目
 * M表示你的初始的资金
 * 说明:每做完一个项目,马上获得的收益,可以支持你去做下一个项目,但不能并行的做项目
 * 输出:你最后获得的最大钱数
 *
 * 贪心策略:
 * 先把(花费,利润)对象, 按花费排序放至小根堆中, 锁定项目小根堆
 * 再准备一个存放(花费,利润)对象, 按利润排序放至大根堆中, 解锁项目大根堆
 * 根据启动资金M, 从"锁定项目小根堆"中获取可以解锁的项目放至"解锁项目大根堆"
 * 再在"解锁项目大根堆"中弹出一个项目, K-1,
 * M=利润+M, 再次解锁"锁定项目小根堆"至"解锁项目大根堆", 直至K=0
 *
 */
public class Code05_IPO {

	public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
		PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
		PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
		for (int i = 0; i < Profits.length; i++) {
			minCostQ.add(new Program(Profits[i], Capital[i]));
		}
		//做K个项目
		for (int i = 0; i < K; i++) {
			//根据W判断可以解锁的项目
			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
				maxProfitQ.add(minCostQ.poll());
			}
			if (maxProfitQ.isEmpty()) {
				return W;
			}
			//获取收益(净利润,已扣除了花费)
			W += maxProfitQ.poll().p;
		}
		return W;
	}

	public static class Program {
		//收益
		public int p;
		//花费
		public int c;

		public Program(int p, int c) {
			this.p = p;
			this.c = c;
		}
	}

	//花费小根堆
	public static class MinCostComparator implements Comparator<Program> {

		@Override
		public int compare(Program o1, Program o2) {
			return o1.c - o2.c;
		}

	}

	//收益大根堆
	public static class MaxProfitComparator implements Comparator<Program> {

		@Override
		public int compare(Program o1, Program o2) {
			return o2.p - o1.p;
		}

	}

}
